package lbj.cyw.dp;

public class FindTargetSumWays494 {
    public int findTargetSumWays(int[] nums, int s){
        int sum=0;
        for (int num : nums) {
            sum+=num;
        }
        int neg=(sum-s);
        if(neg<0 || neg%2!=0){
            return 0;
        }
        neg/=2;
        int[] dp=new int[neg+1];
        dp[0]=1;
        for(int i=0;i<nums.length;i++){
            for(int j=neg;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[neg];
    }
}
